package mapplayer.utils.astar
{
	public class AStar
	{
		static public const GOAL:int	= 0;	///< ゴール
		static public const START:int	= 1;	///< スタート
		static public const OPEN:int	= 2;	///< なにもない通れる所
		static public const BLOCK:int	= 3;	///< 通れない

		private var _mapData:Array;
		private var _mapWidth:int;
		private var _mapHeight:int;

		private var _mapNodes:Array;	///< 経路探査に使用するマップノード

		private var startNode:AStarNode;
		private var goalNode:AStarNode;
		private var openList:Array;
		private var closeList:Array;

		public function AStar()
		{
		}

		/// マップデータをセットする
		/// @param data マップのデータ(Array<int>)
 		/// @param width マップの幅
		/// @param height マップの高さ
		public function setMapData(width:int, height:int, data:Array):void
		{
			_mapWidth = width;
			_mapHeight = height;
			_mapData = data;

			_mapNodes = new Array();
			var x:int, y:int;
			for (y=0; y<_mapHeight; y++) {
				for (x=0; x<_mapWidth; x++) {
					var index:int = y*_mapWidth + x;
					var dat:int = _mapData[index];
					var node:AStarNode
					if (dat == 0) {
						// 通れる所
						node = new AStarNode(x, y, AStar.OPEN);
					}
					else {
						// 通れない
						node = new AStarNode(x, y, AStar.BLOCK);
					}
					_mapNodes.push(node);
				}
			}
		}

		/// 経路を返す
		/// @param startX スタートX座標
		/// @param startY スタートY座標
		/// @param goalX ゴールX座標
		/// @param goalY ゴールY座標
		/// @return 経路算出に成功した場合、AStarNodeの配列を返す。たどり着けない場合、nullを返す
		public function getTrail(startX:int, startY:int, goalX:int, goalY:int):Array
		{
			clearNodes();
			openList = new Array();
			closeList = new Array();

			startNode = getNode(startX, startY);
			goalNode = getNode(goalX, goalY);
			
			// スタート、もしくはゴールノードが見つからない
			if (startNode == null || goalNode == null) {
				return null;
			}

			startNode.state = AStar.START;
			goalNode.state = AStar.GOAL;

			startNode.f_star = h_star(startNode);

			// Openリストに追加
			openList.push(startNode);
			
			var loopCount:int = 0;
			
			// Openリストが空ならば検索は失敗
			while (openList.length > 0) {
trace ("loopCount = "+ loopCount);
				// f_starが最小の値の者を探す
				openList.sortOn("f_star", Array.NUMERIC);
				var n:AStarNode = openList[0];

				// GOALだったら検索終了
				if (n.isGoalNode()) {
					break;
				}

				// Closeリストへnを移す
				openList.shift();
				closeList.push(n);

				// 隣接ノードの配列を作る
				var mNodeArray:Array = getMNodeArray(n);

				var i:int;
				for (i=0; i<mNodeArray.length; i++) {
					var m:AStarNode = mNodeArray[i];
					// f_starを計算
					m.f_star = (n.f_star - h_star(n)) + h_star(m) + cost(n,m);

					// 条件分岐
					var openIndex:int = isOpenList(m);
					var closeIndex:int = isCloseList(m);
					var oldM:AStarNode;

					// openListにもcloseListにもmがない
					if (openIndex<0 && closeIndex<0) {
						m.parent = n;
						openList.push(m);
					}
					else
					// openListにある
					if (openIndex >= 0) {
						oldM = openList[openIndex];
						if (m.f_star < oldM.f_star) {
							openList[openIndex] = m;
						}
					}
					else
					// closeListにある
					if (closeIndex >=0) {
						oldM = closeList[closeIndex];
						if (m.f_star < oldM.f_star) {
							// closeから削除(mが入っていた所を先頭の0で上書きして、先頭削除
							closeList[closeIndex] = closeList[0];
							closeList.shift();
							// openへ
							openList.push(m);
						}
					}

				}

				// 無限ループ回避措置（バグ回避用）
				loopCount ++;
				if (loopCount > 1000) {
					trace ("WARN: fail to find route.");
					return null;
				}

				trace (" ... openList.length = " + openList.length);
			}

			if (openList.length == 0) {
				trace ("WARN: 検索失敗");
			}
//trace ("openList = " + openList);

			// 経路を並び替えて	返り値となる配列を作る
			var res:Array = new Array();
			var node:AStarNode = openList[0];
			while(node.parent != null) {
				res.push(node);
				node = node.parent;
			}
			res.reverse();

			openList = null;
			closeList = null;

			return res;
		}

		/// mからnに移動した時のコストを計算する
		private function cost(m:AStarNode, n:AStarNode):int {
			var dx:int = Math.abs(m.x - n.x);
			var dy:int = Math.abs(m.y - n.y);
			return dx + dy;
		}

		/// h*を計算する
		private function h_star(node:AStarNode):int {
			return cost(goalNode, node);
		}

		/// ノードの取得
		private function getNode(x:int, y:int):AStarNode
		{
			if (x<0 || y<0 || x>=_mapWidth || y>=_mapHeight) {
				return null;
			}

			var index:int = y*_mapWidth + x;
			return _mapNodes[index];
		}

		/// ノードのデータを初期化する
		private function clearNodes():void
		{
			var num:int = _mapWidth * _mapHeight;
			for (var i:int=0; i<num; i++) {
				_mapNodes[i].clear();
			}
		}

		/// 隣接するノードの配列を返す
		private function getMNodeArray(node:AStarNode):Array
		{
			var res:Array = new Array();
			var movex:Array = [-1, 0, 1, 0];
			var movey:Array = [0, 1, 0, -1];
			for (var i:int=0; i<movex.length; i++) {
				var n:AStarNode = getNode(node.x+movex[i], node.y+movey[i]);
				if (n == null) continue;
				if (!n.isWalk()) continue;
				res.push(n);
			}
			return res;
		}

		/// openList中に指定のノードがあるか判定
		/// @return 見つかった場合、インデックス番号を返す。見つからない場合-1を返す。
		private function isOpenList(node:AStarNode):int
		{
			var i:int;
			for (i=0; i<openList.length; i++) {
				var n:AStarNode = openList[i];
				if (n.x == node.x && n.y == node.y) return i;
			}
			return -1;
		}

		/// closeList中に指定のノードがあるか判定
		/// @return 見つかった場合、インデックス番号を返す。見つからない場合-1を返す。
		private function isCloseList(node:AStarNode):int
		{
			var i:int;
			for (i=0; i<closeList.length; i++) {
				var n:AStarNode = closeList[i];
				if (n.x == node.x && n.y == node.y) return i;
			}
			return -1;
		}
	}
}